package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/insert-interval/description/?envType=study-plan-v2&envId=top-interview-150">插入区间(Insert Interval)</a>
 * <p>给你一个 无重叠的 ，按照区间起始端点排序的区间列表。</p>
 * <p>在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
 *      输出：[[1,5],[6,9]]
 *
 * 示例 2：
 *      输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
 *      输出：[[1,2],[3,10],[12,16]]
 *      解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
 *
 * 示例 3：
 *      输入：intervals = [], newInterval = [5,7]
 *      输出：[[5,7]]
 *
 * 示例 4：
 *      输入：intervals = [[1,5]], newInterval = [2,3]
 *      输出：[[1,5]]
 *
 * 示例 5：
 *      输入：intervals = [[1,5]], newInterval = [2,7]
 *      输出：[[1,7]]
 *     </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= intervals.length <= 10^4</li>
 *         <li>intervals[i].length == 2</li>
 *         <li>0 <= intervals[i][0] <= intervals[i][1] <= 10^5</li>
 *         <li>intervals 根据 intervals[i][0] 按 升序 排列</li>
 *         <li>newInterval.length == 2</li>
 *         <li>0 <= newInterval[0] <= newInterval[1] <= 10^5</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/16 19:17
 */
public class LC0057InsertInterval_M {

    static class Solution {
        public int[][] insert(int[][] intervals, int[] newInterval) {
            List<int[]> retList = new ArrayList<>();
            int left = newInterval[0];
            int right = newInterval[1];
            boolean placed = false;
            for (int[] interval : intervals) {
                if (interval[0] > right) {
                    // 1.如果当前范围在newInterval的右侧，且无交集
                    if (!placed) {
                        retList.add(new int[]{left, right});
                        placed = true;
                    }
                    retList.add(interval);
                } else if (left > interval[1]) {
                    // 2.如果当前范围在newInterval的左侧，且无交集
                    retList.add(interval);
                } else {
                    // 3.与插入区间有交集，计算它们的并集
                    left = Math.min(left, interval[0]);
                    right = Math.max(right, interval[1]);
                }
            }
            if (!placed) {
                retList.add(new int[]{left, right});
            }
            int[][] retArr = new int[retList.size()][2];
            for (int i = 0; i < retList.size(); ++i) {
                retArr[i] = retList.get(i);
            }
            return retArr;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[][] insert;
        insert = solution.insert(new int[][]{{1, 3}, {6, 9}}, new int[]{2, 5});
        for (int i = 0; i < insert.length; i++) {
            System.out.print("(" + insert[i][0] + "," + insert[i][1] + ")  ");
            if (i == insert.length - 1) {
                System.out.println();
            }
        }
        insert = solution.insert(new int[][]{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}, new int[]{4, 8});
        for (int i = 0; i < insert.length; i++) {
            System.out.print("(" + insert[i][0] + "," + insert[i][1] + ")  ");
            if (i == insert.length - 1) {
                System.out.println();
            }
        }

        insert = solution.insert(new int[][]{}, new int[]{5, 7});
        for (int i = 0; i < insert.length; i++) {
            System.out.print("(" + insert[i][0] + "," + insert[i][1] + ")  ");
            if (i == insert.length - 1) {
                System.out.println();
            }
        }

        insert = solution.insert(new int[][]{{1, 5}}, new int[]{2, 3});
        for (int i = 0; i < insert.length; i++) {
            System.out.print("(" + insert[i][0] + "," + insert[i][1] + ")  ");
            if (i == insert.length - 1) {
                System.out.println();
            }
        }

        insert = solution.insert(new int[][]{{1, 5}}, new int[]{2, 7});
        for (int i = 0; i < insert.length; i++) {
            System.out.print("(" + insert[i][0] + "," + insert[i][1] + ")  ");
            if (i == insert.length - 1) {
                System.out.println();
            }
        }
    }
}
